import java.util.Arrays;

public class MaxSubarraySum {
    
    /**
     * 使用动态规划求最大子数组和
     */
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
    
    public static void main(String[] args) {
        // 测试用例
        int[][] testCases = {
            {1, -2, 3, 5, -1},
            {1, -2, 3, -8, 5, 1},
            {1, -2, 3, -2, 5, 1}
        };
        
        for (int i = 0; i < testCases.length; i++) {
            int result = maxSubArray(testCases[i]);
            System.out.printf("测试%d %s: 结果=%d%n", 
                i+1, Arrays.toString(testCases[i]), result);
        }
    }
}